"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        c_node = Node(node.val)
        self.cp_map = {node: c_node}
        self._clone_graph(node, c_node)
        return c_node

    def _clone_graph(self, node, c_node):
        c_neighbors = []
        for n in node.neighbors:
            if n not in self.cp_map:
                self.cp_map[n] = Node(n.val)
                self._clone_graph(n, self.cp_map[n])
            c_neighbors.append(self.cp_map[n])
        c_node.neighbors = c_neighbors
